//public class TestDemo {
//    public static void main1(String[] args) {
//        int a=10;
//        double b=3.14;
//        char c='A';
//        int d=20;
//        int e=30;
//        System.out.println(a);
//        System.out.println(b);
//        System.out.println(c );
//        System.out.println(d);
//        System.out.println(e)   ;
//
//
//        long c1 = 10L  ;
//        long d1 = 10l ;
//        System.out.println(Long.MIN_VALUE);
//        System.out .println(Long.MAX_VALUE);
//    }
//}

//public class TestDemo {
//
//
//
//    public static void main(String[] args) {
//
//        System.out.println("hello");
//

//    }
//
//
//
//}


//public class TestDemo {
//    public static void main(String[] args) {
//        int count=0;
//        for (int i = 1; i <=100; i++) {
//            if(i/10==9){
//                count++;
//            }else if( i % 10==9){
//                count++;
//            }
//        }
//        System.out.println(count);
//    }
//}


//}




 /*

多行注释：

        1. main方法是Java程序的入口方法

        2. main函数的格式是固定的，必须为public static void main(String[] args)

        */


import javax.imageio.stream.ImageInputStream;
import javax.swing.*;
import java.util.Arrays;
import java.util.Random;
import java.util.Scanner;

/**
      文档注释:
         main方法是程序的入口函数

      。

         */

// 单行注释：System.out.println是Java中标准输出，会将内容输出到控制台
//        public class TestDemo {
//
//
//            public static void main(String[] args ) {
//
//
//                System.out.println( "hello"   );
//
//            }
//        }


//public class TestDemo {
//    //计算1/1-1/2+1/3-1/4+1/5 …… + 1/99 - 1/100 的值
//            public static void main(String[] args) {
//               double sum = 0;
//                for (int i = 1; i <= 100 ; i++) {
//                    if(i % 2 == 1) {
//                        sum += 1.0 / i;
//                    }else if(i % 2 == 0){
//                        sum -= 1.0 / i;
//                    }
//                }
//                System.out.println(sum);
//            }
//}


//实现猜数字游戏
//public class TestDemo {
//            public static void main(String[] args) {
//                Random random = new Random();
//                Scanner scanner = new Scanner(System.in);
//                int randNum = random.nextInt(101);
//                while(true){
//                    System.out.println("请输入你要猜的数字");
//                    int sum = scanner.nextInt();
//                    if(sum < randNum){
//                        System.out.println("猜小了");
//                    }else if(sum == randNum){
//                        System.out.println("猜对了");
//                        break;
//                    }else{
//                        System.out.println("猜大了");
//                    }
//                }
//
//            }
//}

//public class TestDemo {
//    //打印 X 图形
//    public static void main(String[] args) {
//        Scanner scanner = new Scanner(System.in);
//        while(true){
//            int sum = scanner.nextInt();
//            for (int i = 1; i <= sum; i++) {
//                for (int j = 1; j <= sum ; j++) {
//                    if(i == j || i+j == sum+1){
//                        System.out.print("*");
//                    }else {
//                        System.out.print(" ");
//                    }
//                }
//                System.out.println();
//            }
//
//        }
//    }
//}

//public class TestDemo {
//    //输出一个整数的每一位
//    public static void main(String[] args) {
//        Scanner scanner = new Scanner(System.in);
//        int sum = scanner.nextInt();
//        int ret = 0;
//        while(true){
//            ret = sum % 10;
//            System.out.println(ret);
//            sum = sum / 10;
//            if(sum % 10 == 0){
//                break;
//            }
//        }
//
//    }
//}

//public class TestDemo {
//    //模拟登陆
//    public static void main(String[] args) {
//        Scanner scanner = new Scanner(System.in);
//        int count = 3;
//        while(count != 0){
//            System.out.println("请输入密码：你还有"+count+"次机会");
//            String pass = scanner.nextLine();
//            if(pass.equals("12345")){
//                System.out.println("密码正确");
//                break;
//            }else{
//                System.out.println("密码错误");
//                count--;
//            }
//        }
//    }
//}


//public class TestDemo {
//    //求2个整数的最大公约数
//    public static void main(String[] args) {
//        int a = 20;
//        int b = 40;
//        int c = a % b;
//        while (c != 0) {
//            a = b;
//            b = c;
//            c = a % b;
//        }
//        System.out.println(b);
//    }
//}

//public class TestDemo {
//    public static void main(String[] args) {
//        System.out.println(Integer.MIN_VALUE);
//
//
//        System.out.println(Integer.MAX_VALUE);
//    }
//}
//


//public class TestDemo {
//    public static void main(String[] args) {
//        String s1 = "hello";
//        String s2 = " world";
//        System.out.println(s1);
//        System.out.println(s2);
//        System.out.println(s1+s2);  // s1+s2表示：将s1和s2进行拼接
//
//
//        int num = 10;
//// 方法1
//        String str1 = num + "";//此时这个加号就是拼接的意思
//        System.out.println(str1);
//
//// 方法2
//        String str2 = String.valueOf(num);//调用String这个类型的方法
//        System.out.println(str2);
//
//        String s3 = 10+20+"x";
//        String s4 = "x"+10+20;
//        System.out.println(s3);
//        System.out.println(s4);
//        System.out.println("==========");
//        String str = "100";
//
//        int num1 = Integer.parseInt(str);
//        System.out.println(num1);
//
//    }
//}



//public class TestDemo {
//    public static void main(String[] args) {
//        int a = 20;
//
//        int b = 10;
//
//
//        System.out.println(a + b);     // 30
//
//        System.out.println(a - b);     // 10
//
//        System.out.println(a * b);     // 200
//
//        System.out.println(a / b);     // 2
//
//        System.out.println(a % b);     // 0 --->模运算相当于数学中除法的余数

//        int a = 3;
//
//        int b = 2;
//        System.out.println(a / b);
//        double d = a*1.0 / b;
//
//        System.out.println(d);

//        System.out.println(10%3);
//        System.out.println(10%-3);
//        System.out.println(-10%3);
//        System.out.println(-10%-3);
//        System.out.println(11.5 % 2);

//        int a = 1;
//
//        int b = 0;
//
//        System.out.println(a / b);
//        long d = 100;
//        int c = 9;
//        c += d;//c = (int)(c + d) 特点：运算符会帮我们进行类型转换
//        System.out.println(c);


//        int a = 1;
//        int b = a++;    // 后置++   表示给a的值加1，此时a的值为2
//        System.out.println(a++);   // 注意：后置++是先使用变量原来值，表示式结束时给变量+1，因此输出1
//
//        System.out.println(b);     // 输出1


//        int a = 1;
//        int b = ++a;    // 前置++   表示给a的值加1
//        //a = a + 1  b = a
//        System.out.println(++a);   // 注意：前置++是先给变量+1，然后使用变量中的值，因此输出5
//
//        System.out.println(b);     // 输出5


//        int a = 10;
//        int b = 20;
//
//// 注意：在Java中 = 表示赋值，要与数学中的含义区分
////     在Java中 == 表示相等
//
//        System.out.println(a == b);       // false
//
//        System.out.println(a != b);       // true
//
//        System.out.println(a < b);        // true
//
//        System.out.println(a > b);        // false
//
//        System.out.println(a <= b);       // true
//
//        System.out.println(a >= b);       // false
//
//        System.out.println(3 < a < 5);



//        int a = 1;
//
//        int b = 2;
//
//
//        System.out.println(a == 1 && b == 2);  // 左为真 且 右为真 则结果为真
//
//        System.out.println(a == 1 && b > 100); // 左为真 但 右为假 则结果为假
//
//        System.out.println(a > 100 && b == 2); // 左为假 但 右为真 则结果为假
//
//        System.out.println(a > 100 && b > 100); // 左为假 且 右为假 则结果为假


//        int a = 1;
//        int b = 2;
//
//        System.out.println(a == 1 || b == 2);   // 左为真 且 右为真 则结果为真
//        System.out.println(a == 1 || b > 100);  // 左为真 但 右为假 则结果也为真
//        System.out.println(a > 100 || b == 2);  // 左为假 但 右为真 则结果也为真
//        System.out.println(a > 100 || b > 100); // 左为假 且 右为假 则结果为假

//        System.out.println(10 > 20 && 10 / 0 == 0);        // 打印 false
//        System.out.println(10 < 20 || 10 / 0 == 0);       // 打印 true



//        System.out.println(10 > 20 & 10 / 0 == 0);             // 程序抛出异常
//
//        System.out.println(10 < 20 | 10 / 0 == 0);             // 程序抛出异常

//        int a = 10;
//
//        int b = 20;
//
//        System.out.println(a & b);


//        int a = 10;
//
//        int b = 20;
//
//        System.out.println(a | b);

//        int a = 0xf;
//
//        System.out.printf("%x\n", ~a );


//        int a = 0x1;
//
//        int b = 0x2;
//
//        System.out.printf("%x\n", a ^ b);


        // 求两个整数的最大值

//        int a = 10;
//
//        int b = 20;
//
//        int max = a > b ? a : b;
//        System.out.println(max);


//      int score=0;
//        if(score >= 90){
//            System.out.println("优秀");
//        }else if(score >= 80 && score < 90){
//            System.out.println("良好");
//        }else if(score >= 70 && score < 80){
//            System.out.println("中等");
//        }else if(score >= 60 && score < 70){
//            System.out.println("及格");
//        }else if(score >= 0 && score < 60){
//            System.out.println("不及格");
//        }else{
//            System.out.println("错误数据");
//        }




//        int score = 92;
//
//        if(score >= 90){
//            System.out.println("吃个大鸡腿!!!");
//        }else{
//            System.out.println("被家长说!!!");
//        }
//
//
//
//    }
//}



//public class TestDemo {
//    public static void main(String[] args) {
//        int num = 1;
//        while(num <= 10){
//            System.out.println(num);
//            num++;
//        }

//        int n = 1;
//        int ret = 1;
//        while(n <= 5){
//            ret = ret * n;
//            n++;
//        }
//        System.out.println(ret);
//        int k =1;
//        int sum = 0;
//        // 外层循环负责求阶乘的和
//        while(k <= 5) {
//            int n = 1;
//            int ret = 1;
//            // 里层循环负责完成求阶乘的细节.
//            while (n <= k) {
//                ret = ret * n;
//                n++;
//            }
//            k++;
//            sum = sum + ret;
//        }
//        System.out.println(sum);

//        int num = 100;
//
//        while (num <= 200) {
//            if (num % 3 == 0) {
//                System.out.println("找到了 3 的倍数, 为:" + num);
//                break;
//            }
//            num++;
//        }


//        int num = 100;
//
//        while (num <= 200) {
//            if (num % 3 != 0) {
//                num++;  // 这里的 ++ 不要忘记! 否则会死循环.
//
//                continue;
//            }
//            System.out.println("找到了 3 的倍数, 为:" + num);
//            num++;
//        }


//        int n = 1;
//        while (n <= 5){
//            if (n == 2){
//                n++;
//                continue;
//            }
//            System.out.println(n);
//            n++;
//        }


//        int i = 100;
//        while (i <= 200) {
//            if(i % 12 != 0) {
//                i++;
//                continue;
//            }
//            System.out.println(i);
//            i++;
//        }

//        int sum = 0;
//
//        for (int i = 1; i <= 100; i++) {
//            sum += i;
//        }
//
//        System.out.println("sum = " + sum);

//        int result = 1;
//
//        for (int i = 1; i <= 5; i++) {
//            result *= i;
//        }
//
//        System.out.println("result = " + result);

//        int sum = 0;
//
//        for (int i = 1; i <= 5; i++) {
//            int tmp = 1;
//            for (int j = 1; j <= i; j++) {
//                tmp *= j;
//            }
//            sum += tmp;
//        }
//
//        System.out.println("sum = " + sum);

//        int num = 1;
//
//        do {
//            System.out.println(num);
//            num++;
//        } while (num <= 10 );

//        System.out.println("hello world");
//
//
//        int x = 10;
//
//        System.out.printf("x = %d\n", x);

//        Scanner scan = new Scanner(System.in);
//        System.out.println("输入一个年龄：");
//        int age = scan.nextInt();//读入一个int类型的整数
//        System.out.println("年龄："+age);
//
//        scan.nextLine();//注意回车
//        //nextLine读数据会把上一行的回车读进去，为了消除这个影响，我们手动输入一个nextLine
//        System.out.println("请输入你的姓名：");
//        String name = scan.nextLine();//nextLine 读入一行  next是遇到空格结束！
//        System.out.println("姓名："+name);
//
//        System.out.println("请输入你的工资：");
//        float salary = scan.nextFloat();
//        System.out.println("工资："+salary);
//        scan.close();//可以认为scan是一个资源
//
//        Scanner scan = new Scanner(System.in);
//        while (scan.hasNextInt()) {
//            int age = scan.nextInt();
//            System.out.println(age);
//
//        }



//    }
//}


//public class TestDemo {
//    public static void main(String[] args) {
//        int n = 19;
//        int i = 2;
//        for (; i <=Math.sqrt(n) ; i++) {
//            if (n % i == 0){
//                break;
//            }
//        }
//        //有两种情况  1、 不符合循环条件 2、因为遇到了 break
//        if (i > Math.sqrt(n)){
//            System.out.println(n + " 是素数！ ");
//        }


//        for (int n = 1; n <= 100; n++) {
//            //int n = 9;
//            int i = 2;
//            for (; i <= Math.sqrt(n); i++) {
//                if(n % i == 0) {
//                    break;
//                }
//            }
//            //有几种情况 ？ 2--》  1、 不符合循环条件 2、因为遇到了 break
//            if(i > Math.sqrt(n)) {
//                System.out.println(n + " 是素数！ ");
//            }
//        }


//        for (int i = 1; i <= 999999; i++) {
//            //i == 123
//            int count = 0;//记录位数
//            int tmp = i;
//            while (tmp != 0) {
//                tmp /= 10;
//                count++;
//            }
//            tmp = i;//123
//            int sum = 0;
//            while (tmp != 0) {
//                sum += Math.pow(tmp % 10, count);
//                tmp /= 10;
//            }
//            if (sum == i) {
//                System.out.println(i);
//            }
//        }




//        int n = -1;
//        int count = 0;
//        while (n != 0) {
//            n = n & (n-1);
//            count++;
//        }
//        System.out.println(count);
//    }
//}

//public class TestDemo {
//    public static boolean isLeapYear(int year) {
//        if ((0 == year % 4 && 0 != year % 100) || 0 == year % 400) {
//            //System.out.println(year+"年是闰年");
//            return true;
//        }
//        return false;
//    }
//}

//public class TestDemo {
//     // 方法的定义
//
//        public static int add( int x, int y ) {
//
//            return x + y  ;
//
//
//
//        }
//}



//public class TestDemo {
//    public static void main(String[] args) {
//        int a = 10;
//        int b = 20;
//        System.out.println("第一次调用方法之前");
//        int ret = add(a, b);
//        System.out.println("第一次调用方法之后");
//        System.out.println("ret = " + ret);
//
//        System.out.println("第二次调用方法之前");
//        ret = add(30, 50);
//        System.out.println("第二次调用方法之后");
//        System.out.println("ret = " + ret);
//
//    }
//    public static int add(int x, int y) {
//        System.out.println("调用方法中 x = " + x + " y = " + y);
//        return x + y;
//    }
//
//}

//public class TestDemo {
//        public static int facSum(int n) {
//            int sum = 0;
//            for (int i = 1; i <= 5; i++) {
//                sum += fac(i);
//            }
//            return sum;
//        }
//
//        public static int fac(int n) {
//            int ret = 1;
//            for (int i = 1; i <= n; i++) {
//                ret *= i;
//            }
//            return ret;
//        }
//    public static void main(String[] args) {
//        int n = 5;
//
//        System.out.println(facSum(n));
//
//
//    }
//}
//
//


//public class TestDemo {
//    public static void main(String[] args) {
//        int a = 10;
//        int b = 20;
//        swap(a, b);
//        System.out.println("main: a = " + a + " b = " + b);
//    }
//
//    public static void swap(int x, int y) {
//        int tmp = x;
//        x = y;
//        y = tmp;
//        System.out.println("swap: x = " + x + " y = " + y);
//    }
//}


//public class TestDemo {
//    public static void swap(int x,int y) {
//        int tmp = x;
//        x = y;
//        y = tmp;
//    }
//    public static void main(String[] args) {
//        int a = 10;
//        int b = 20;
//        System.out.println(a+" "+ b);
//        swap(a,b);
//        System.out.println(a+" "+ b);
//    }
//}

//public class TestDemo {
//    public static void main(String[] args) {
//        int[] arr = {10, 20};
//        swap(arr);
//        System.out.println("arr[0] = " + arr[0] + " arr[1] = " + arr[1]);
//    }
//
//    public static void swap(int[] arr) {
//        int tmp = arr[0];
//        arr[0] = arr[1];
//        arr[1] = tmp;
//    }
//}



//public class TestDemo {
//    public static void main(String[] args) {
//        int a = 10;
//        int b = 20;
//        print(a, b);
//    }
//    public static void print(int x, int y) {
//        System.out.println("x = " + x + " y = " + y);
//    }
//}


//public class TestDemo {
//    public static void main(String[] args) {
//        add(1, 2);                // 调用add(int, int)
//
//        add(1.5, 2.5);            // 调用add(double, double)
//
//        add(1.5, 2.5, 3.5);       // 调用add(double, double, double)
//
//    }
//
//    public static int add(int x, int y) {
//        return x + y;
//    }
//
//    public static double add(double x, double y) {
//        return x + y;
//    }
//
//    public static double add(double x, double y, double z) {
//        return x + y + z;
//    }
//}


//public class TestDemo {
//    public static int add(int x, int y){
//        return x + y;
//    }
//
//    public static double add(double x, double y){
//        return x + y;
//    }
//
//    public static void main(String[] args) {
//        add(1,2);
//        add(1.5, 2.5);
//    }
//}

//public class TestDemo {
//    public static void main(String[] args) {
//        int n = 5;
//        int ret = factor(n);
//        System.out.println("ret = " + ret);
//    }
//
//
//    public static int factor(int n) {
//        if (n == 1) {
//            return 1;
//        }
//        return n * factor(n - 1); // factor 调用函数自身
//
//    }
//}



    //按顺序打印一个数字的每一位(例如 1234 打印出 1 2 3 4)
//public class TestDemo {
//    public static void print(int num) {
//        if (num > 9) {
//            print(num / 10);
//        }
//
//        System.out.println(num % 10);
//    }
//
//    public static void main(String[] args) {
//        print(1234);
//
//    }
//}



//递归求 1 + 2 + 3 + ... + 10
//public class TestDemo {
//    public static int sum(int num) {
//        if (num == 1) {
//            return 1;
//        }
//      int tmp = num + sum(num - 1);
//        return tmp;
//    }
//    public static void main(String[] args) {
//        System.out.println(sum(10));
//    }
//}



//输入 1729, 则应该返回1+7+2+9，它的和是19
//public class TestDemo {
//
//    public static int sum(int num) {
//        if (num < 10) {
//            return num;
//        }
//        return num % 10 + sum(num / 10);
//    }
//    public static void main(String[] args) {
//        System.out.println(sum(1729));
//    }
//}




//斐波那契数列
//public class TestDemo {
//    public static int fib(int n) {
//        if (n == 1) {
//            return 0;
//        }
//        if (n == 2) {
//            return 1;
//        }
//        return fib(n - 1) + fib(n - 2);
//    }
//    public static void main(String[] args) {
//        System.out.println(fib(1));
//        System.out.println(fib(2));
//        System.out.println(fib(3));
//        System.out.println(fib(4));
//        System.out.println(fib(40));
//    }
//}



//计算斐波那契的重复计算次数
//public class TestDemo {
//    public static int count = 0;
//    public static int fib(int n) {
//        if (n == 1) {
//            count ++;
//            return 0;
//        }
//        if (n == 2) {
//            count ++;
//            return 1;
//        }
//        return fib(n - 1) + fib(n - 2);
//    }
//    public static void main(String[] args) {
//        System.out.println(fib(40));
//        System.out.println(count);
//    }
//}



//使用循环求斐波那契数
//public class TestDemo {
//    public static int fib(int n) {
//        if (n == 1) {
//            return 0;
//        }
//        if (n == 2) {
//         return 1;
//        }
//        int f1 = 0;
//        int f2 = 1;
//        int f3 = -1;
//        for (int i = 3; i <= n; i++) {
//            f3 = f1 + f2;
//            f1 = f2;
//            f2 = f3;
//        }
//        return f3;
//    }
//
//    public static void main(String[] args) {
//        System.out.println(fib(41));
//    }
//}




//public class TestDemo {
//    public static void main(String[] args) {
////        int[] array = {1,2,3,4};
////        int[] array2 = new int[10];
////        int[] array3 = new int[]{1,2,3,4,5,6,7,};
//        int[] array1 = new int[]{0,1,2,3,4,5,6,7,8,9};
//
//        double[] array2 = new double[]{1.0, 2.0, 3.0, 4.0, 5.0};
//
//        String[] array3 = new String[]{"hell", "Java", "!!!"};
//
//        System.out.println(array1);
//
//        System.out.println(array2);
//        System.out.println(array3);
//    }
//}


//public class TestDemo {
//    public static void func() {
//        int a = 10;
//        int b = 20;
//        int[] array = new int[]{1,2,3};
//
//    }
//
//    public static void main(String[] args) {
//
//
//    }
//}




//public class TestDemo {
//    public static void main(String[] args) {
//        int[] array = {1,2,3,4};
//        int[] array2 = array;
//
//    }
//}



//public class TestDemo {
//    public static void func1(int[] array) {
//        array = new int[10];
//    }
//
//    public static void func2(int[] array) {
//        array[0] = 99;
//    }
//    public static void main(String[] args) {
//        int[] array1 = {1,2,3,4};
//        func1(array1);
//        for (int i = 0; i < array1.length; i++) {
//            System.out.println(array1[i]+" ");
//        }
//        System.out.println();
//        int[] array2 = {1,2,3,4};
//        func2(array2);
//        for (int i = 0; i < array2.length; i++) {
//            System.out.println(array2[i]+" ");
//        }
//        System.out.println();
//    }
//}
//public class TestDemo {
//    public static int[] func3() {
//        int[] array = {1, 2, 3, 4,5,6};
//        return array;
//    }
//
//    public static void main(String[] args) {
//        int[] ret = func3();
//        for (int i = 0; i < ret.length; i++) {
//            System.out.print(ret[i]+" ");
//        }
//    }
//}

//数组转化为字符串
//public class TestDemo {
//    public static int[] func() {
//        return new int[]{1,2,3,4,5,6};
//    }
//    public static void main(String[] args) {
//        int[] ret = func();
//
//        //这个方法主要将参数的数组转化为字符串输出
//       String s = Arrays.toString(ret);
//        //Ctrl+鼠标点击，可以跳转到这个方法的原码
//
//        System.out.println(s);
//    }
//}
//public class TestDemo {
//
//    public static String myToString(int[] array){
//        String ret = "[";
//        for (int i = 0; i < array.length; i++) {
//            ret += array[i];
//           if (i != array.length -1){
//               ret += ",";
//           }
//        }
//        ret += "]";
//        return ret;
//    }
//    public static void main(String[] args) {
//        int[] array = {1,2,3,4,5};
//        String ret = myToString(array);
//        System.out.println(ret);
//    }
//}



//数组拷贝

//public class TestDemo {
//    public static void main(String[] args) {
//        int[] array = {1,2,3,4,5};
//        int[] copy = new int[array.length];
//        for (int i = 0; i < array.length; i++) {
//            copy[i] = array[i];
//        }
//        System.out.println(Arrays.toString(copy));
//    }
//}



//public class TestDemo {
//    public static void main(String[] args) {
//        int[] array = {1,2,3,4,5};
//        int[] copy = Arrays.copyOf(array,array.length);
//        System.out.println(Arrays.toString(copy));
//
//    }
//}


//public class TestDemo {
//    public static void main(String[] args) {
//        int[] array = {1,2,3,4,5};
//        int[] copy = Arrays.copyOf(array,array.length*2);
//        System.out.println(Arrays.toString(copy));
//    }
//}


//public class TestDemo {
//    public static void main(String[] args) {
//        int[] array = {1,2,3,4,5};
//        //取下标为1到3的数字
//        int[] copy = Arrays.copyOfRange(array,1,3);
//        System.out.println(Arrays.toString(copy));
//    }
//}

//public class TestDemo {
//    public static void main(String[] args) {
//        int[] array = {1,2,3,4,5};
//        int[] copy = new int[array.length];
//        System.arraycopy(array,0,copy,0,array.length);
//        System.out.println(Arrays.toString(copy));
//    }
//}
//public class TestDemo {
//    public static void main(String[] args) {
//        int[] array = {1,3,2,6,4,5};
//        Arrays.sort(array);
//        System.out.println(Arrays.toString(array));
//    }
//}



//public class TestDemo {
//    public static void main(String[] args) {
//        int[] array = {1,3,2,6,4,5};
//        Arrays.sort(array);
//        System.out.println(Arrays.binarySearch(array,5));
//    }
//}


//public class TestDemo {
//    public static void main(String[] args) {
////        int[] array1 = {1,2,3,4,5};
////        int[] array2 = {1,2,3,4,5};
////        boolean flg = Arrays.equals(array1,array2);
////        System.out.println(flg);
//        int[] array3 = new int[10];
//        Arrays.fill(array3,1,4,-1);
//        System.out.println(Arrays.toString(array3));
//
//    }
//}



//public class TestDemo {
//    public static void bubbleSort(int[] array) {
//        //i代表的是趟数！！
//        for (int i = 0; i < array.length-1; i++) {
//            //j代表每一趟比较的次数
//            boolean flg = false;
//            for (int j = 0; j < array.length-1-i; j++) {
//                if(array[j] > array[j+1]) {
//                    int tmp = array[j];
//                    array[j] = array[j+1];
//                    array[j+1] = tmp;
//                    flg = true;
//                }
//            }
//            if(flg == false) {
//                break;//说明有序了！！！
//            }
//        }
//    }
//    public static void main(String[] args) {
//        int[] arr = {9, 5, 2, 7};
//        bubbleSort(arr);
//        System.out.println(Arrays.toString(arr));
//    }
//}


//public class TestDemo {
//    public static void main(String[] args) {
//        int[] arr = {1, 2, 3, 4};
//        reverse(arr);
//        System.out.println(Arrays.toString(arr));
//    }
//    public static void reverse(int[] arr) {
//        int left = 0;
//        int right = arr.length - 1;
//        while (left < right) {
//            int tmp = arr[left];
//            arr[left] = arr[right];
//            arr[right] = tmp;
//            left++;
//            right--;
//        }
//    }
//}



//public class TestDemo {
//    public static void main(String[] args) {
//        int[][] arr = {
//                {1, 2, 3, 4},
//                {5, 6, 7, 8},
//                {9, 10, 11, 12}
//        };
//        for (int i = 0; i < arr.length; i++) {
//            for (int j = 0; j < arr[i].length; j++) {
//                System.out.printf("%d\t", arr[i][j]);
//            }
//            System.out.println("");
//        }

        //直接打印二维数组
//        System.out.println(Arrays.deepToString(arr));
//    }
//}




//public class TestDemo {
//    public static void main(String[] args) {
//        int[][] array = new int[2][];
//        array[0] = new int[]{1,2,3};
//        array[1] = new int[]{4,5,6,7,8,9};
//
//        System.out.println(Arrays.deepToString(array));
//    }
//}

//class Solution {
//    public int reverse(int x) {
//
//        int res = 0;
//
//        while(x!=0) {
//
//
//            //每次取末尾数字
//            int tmp = x%10;
//
//
//
//            //判断是否 大于 最大32位整数
//            if (res>214748364 || (res==214748364 && tmp>7)) {
//
//
//
//
//                return 0;
//
//            }
//            //判断是否 小于 最小32位整数
//            if (res<-214748364 || (res==-214748364 && tmp<-8)) {
//                return 0;
//
//            }
//            res = res*10 + tmp;
//            x /= 10;
//        }
//
//        return res;
//    }
//
//}


////2207字符串中最多数目的子序列（24.9.24）
//class Solution {
//    public long maximumSubsequenceCount(String s, String pattern) {
//        long res = 0;
//        int cnt1 = 0, cnt2 = 0;
//        for (int i = 0; i < s.length(); ++i) {
//            if (s.charAt(i) == pattern.charAt(1)) {
//                res += cnt1;
//                cnt2++;
//            }
//            if (s.charAt(i) == pattern.charAt(0)) {
//                cnt1++;
//            }
//        }
//        return res + Math.max(cnt1, cnt2);
//    }
//}

////2306公司命名（24.9.25）
//class Solution {
//    public long distinctNames(String[] ideas) {
//        Map<Character, Set<String>> names = new HashMap<Character, Set<String>>();
//        for (String idea : ideas) {
//            names.putIfAbsent(idea.charAt(0), new HashSet<String>());
//            names.get(idea.charAt(0)).add(idea.substring(1));
//        }
//        long ans = 0;
//        for (Map.Entry<Character, Set<String>> entryA : names.entrySet()) {
//            char preA = entryA.getKey();
//            Set<String> setA = entryA.getValue();
//            for (Map.Entry<Character, Set<String>> entryB : names.entrySet()) {
//                char preB = entryB.getKey();
//                Set<String> setB = entryB.getValue();
//                if (preA == preB) {
//                    continue;
//                }
//                int intersect = getIntersectSize(setA, setB);
//                ans += (long) (setA.size() - intersect) * (setB.size() - intersect);
//            }
//        }
//        return ans;
//    }
//
//    public int getIntersectSize(Set<String> a, Set<String> b) {
//        int ans = 0;
//        for (String s : a) {
//            if (b.contains(s)) {
//                ans++;
//            }
//        }
//        return ans;
//    }
//}
//
//
//
//
//
//
//2535数组元素和与数字和的绝对差(24.9.26)
//class Solution {
//    public int differenceOfSum(int[] nums) {
//        int elementSum = 0, digitSum = 0;
//        for (int num : nums) {
//            elementSum += num;
//            while (num > 0) {
//                digitSum += num % 10;
//                num /= 10;
//            }
//        }
//        return elementSum - digitSum;
//    }
//}





////
//import java.util.Map;
//class Solution {
//    Map<Integer, Integer> memo = new HashMap<Integer, Integer>();
//
//    public int superEggDrop(int k, int n) {
//        return dp(k, n);
//    }
//
//    public int dp(int k, int n) {
//        if (!memo.containsKey(n * 100 + k)) {
//            int ans;
//            if (n == 0) {
//                ans = 0;
//            } else if (k == 1) {
//                ans = n;
//            } else {
//                int lo = 1, hi = n;
//                while (lo + 1 < hi) {
//                    int x = (lo + hi) / 2;
//                    int t1 = dp(k - 1, x - 1);
//                    int t2 = dp(k, n - x);
//
//                    if (t1 < t2) {
//                        lo = x;
//                    } else if (t1 > t2) {
//                        hi = x;
//                    } else {
//                        lo = hi = x;
//                    }
//                }
//
//                ans = 1 + Math.min(Math.max(dp(k - 1, lo - 1), dp(k, n - lo)), Math.max(dp(k - 1, hi - 1), dp(k, n - hi)));
//            }
//
//            memo.put(n * 100 + k, ans);
//        }
//
//        return memo.get(n * 100 + k);
//    }
//}


//1547 切棍子最小成本
class Solution {
    public int minCost(int n, int[] cuts) {
        int m = cuts.length;
        Arrays.sort(cuts);
        int[] newCuts = new int[m + 2];
        newCuts[0] = 0;
        for (int i = 1; i <= m; ++i) {
            newCuts[i] = cuts[i - 1];
        }

        newCuts[m + 1] = n;
        int[][] f = new int[m + 2][m + 2];
        for (int i = m; i >= 1; --i) {
            for (int j = i; j <= m; ++j) {
                f[i][j] = i == j ? 0 : Integer.MAX_VALUE;
                for (int k = i; k <= j; ++k) {
                    f[i][j] = Math.min(f[i][j], f[i][k - 1] + f[k + 1][j]);
                }
                f[i][j] += newCuts[j + 1] - newCuts[i - 1];
            }
        }
        return f[1][m];
    }
}






